1. Field of the Disclosure
The present disclosure relates to a method and a device which are capable of performing fast maximum likelihood decoding at low computational complexity by decreasing lost data restored by a Gauss elimination method whenever possible and increasing lost data restored by a trivial decoding method based on a message passing algorithm (MPA) whenever possible in maximum likelihood decoding of a sparse graph code.
2. Discussion of the Background Art
Currently, the error correction technique is widely being used in various kinds of communication systems such as communication in digital satellite broadcasting or the Internet or communication in mobile terminals. Particularly, with the recent development of a broadband environment, for example, a moving image delivery service using the Internet is expected, and the error correction technique became consequential to the Internet. The following description will proceed with the Internet as an example.
If a channel is observed from a side at providing service using the Internet, the Internet may be regarded as an erasure channel (a packet erasure channel (PEC)). This is a channel in which binary erasure channels are grouped in units of packets, and a channel output is output based on correct information at a probability of 1-p or output (lost) as an unidentified # at a probability of p due to a certain failure occurring in a line as illustrated in FIG. 1. In this communication system, a lost packet restoration technique such as forward error correction (FEC) or automatic repeat request (ARQ) is used. In a common IP-based service, a TCP/IP protocol is used, only error detection is performed at a decoder side, and when an error occurs, a method of restoring an error through retransmission control or the like is used (an ARQ scheme). However, when a large-scaled service such as multicast delivery is considered, error correction is required to be performed based on data received by a receiver side, and a method capable of correcting an error only at the reception without requiring a feedback channel is used (a FEC scheme). In the FEC scheme, since retransmission control or the like is not performed, a delay is small, and the FEC scheme is used even in a teleconference system in which a real-time property is important. The following description will proceed with the FEC scheme.
As the FEC scheme, a Reed Solomon code (an RS code) is widely used in digital broadcasting or the like. In Japanese digital broadcasting, a code length of 204 bytes is defined, and tolerance to an error is given by adding parity bytes of about 10% to original data 188 bytes. However, commonly, performance is known to be improved when a code with a large code length is used as an error correction code, but when a code length is long, an adverse effect in which decoding is complicated, and computational complexity enormously increases is also known. For this reason, in the RS code, a code length of 256 bytes or less is assumed to be dealt. Further, when the RS code adapts to a packet called an IP-based packet level FEC, it is necessary to deal 256 packets as a block due to this reason.
On the other hand, a decoding technique based on a message passing algorithm (MPA) is known to have excellent decoding characteristics at practical computational complexity when a code length is long, and a low density parity check (LDPC) code (for example, see Non Patent Literature 1) serving as a linear code defined by a sparse graph has attracted attention as a realistic error correction method approaching to a channel capacity defined by Shannon. Here, the sparse graph is a graph in which the number of edges is much smaller than the number of nodes. Further, as an erasure correction code based on the sparse graph, an LT code of Digital Fountain, Inc. (for example, see Non Patent Literature 2) and a Raptor code (for example, see Non Patent Literature 3) are known, code characteristics capable of decoding by only receiving arbitrary code data without significantly deteriorating coding efficiency are known to be implemented at fulfilling computational complexity. Since this property is suitable for asynchronous layered coding (ALC) (for example, see Non Patent Literature 4) serving as an Internet multicast protocol, it is widely used, for example, in a multicast communication with a layered configuration.    Patent Literature 1: M. Luby, “Information Additive Code Generator and Decoder for Communication Systems,” U.S. Pat. No. 6,307,487, Oct. 23, 2001    Patent Literature 2: M. Luby, “Information Additive Code Generator and Decoder for Communication Systems,” U.S. Pat. No. 6,373,406, Apr. 16, 2002    Patent Literature 3: A. Shokrollahi, S. Lassen, and M. Luby, “Multi-Stage Code Generator and Decoder for Communication Systems,” U.S. Patent Application No. 20030058958, December 2001    Patent Literature 4: A. Shokrollahi, S. Lassen and R. Karp, “Systems and Processes for Decoding Chain Reaction Codes Through Inactivation,” U.S. Pat. No. 6,856,263, Feb. 15, 2005    Patent Literature 5: A. Shokrollahi and M. Luby, “Systematic Encoding and Decoding of Chain Reaction Codes,” U.S. Pat. No. 6,909,383, Jun. 21, 2005 Non Patent Literature    Non Patent Literature 1: R. G. Gallager, “Low density parity check codes,” in Research Monograph series. Cambridge, MIT Press, 1963    Non Patent Literature 2: M. Luby, “LT Codes,” The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002    Non Patent Literature 3: Shokrollahi, A, “Raptor codes,” Information Theory, IEEE Transactions on Volume 52, Issue 6, 2006    Non Patent Literature 4: “Asynchronous layered coding protocol instantiation,” IETF RFC 3450, December 2002    Non Patent Literature 5: E. Paolini, G. Liva, B. Matuz, and M. Chiani, “Maximum likelihood erasure decoding of LDPC codes: pivoting algorithms and code design,” IEEE Trans. Commun. vol. 60, no. 11, pp. 3209 to 3220, November 2012    Non Patent Literature 6: Cunche, M. and V. Roca, “Optimizing the Error Recovery Capabilities of LDPC-Staircase Codes Featuring a Gaussian Elimination Decoding Scheme,” 10th IEEE International Workshop on Signal Processing for Space Communications (SPSC7'08), October 2008